package com.leetcode.普通数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

//合并区间
public class lc_56 {
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {4, 6}, {5, 8}, {10, 12}};
        int[][] result = merge(intervals);
        for (int[] interval : result) {
            System.out.println(Arrays.toString(interval));
        }
    }

    public static int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        //按区间起始点进行排序,sort方法有很多重载方式,这里添加了一个Comparator比较器,实现了一个ToIntFunction接口
        //接口的作用是提取一个int类型的数据作为比较的依据,这里使用区间的start作为比较依据
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        //mergedIntervals用来存储目前为止已经合并好的区间 currentInterval是现在的结果区间,初始为第一个
        List<int[]> mergedIntervals = new ArrayList<>();
        int[] currentInterval = intervals[0];
        //默认情况下遍历到第一个区间,可以直接放入,还没开始合并
        mergedIntervals.add(currentInterval);

        //遍历所有区间开始操作
        for (int i = 1; i < intervals.length; i++) {
            //如果当前遍历区间的起始点在当前结果区间的起始点之后,说明不重叠,将当前的结果区间设为当前遍历区间
            //并直接将这个没有重叠区间的当前的结果区间放入集合
            if (intervals[i][0] > currentInterval[1]) {
                currentInterval = intervals[i];
                mergedIntervals.add(currentInterval);
            } else {
                //如果有重叠,将当前结果区间的end设为当前结果区间和当前遍历区间的最大值
                currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);
            }
        }

        //使用toArray方法,将list集合返回为一个二维数组
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }
}
